#include <iostream>
#include <vector>
#include <climits>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;

pair<vector<vector<int>>, vector<vector<int>>> matrixChainOrder(const vector<int> &dims)
{
    int n = dims.size() - 1;
    vector<vector<int>> m(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));

    for (int l = 2; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; k++)
            {
                int q = m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    return {m, s};
}

string buildOptimalParens(const vector<vector<int>> &s, int i, int j)
{
    if (i == j)
    {
        return to_string(i - 1); // 修正为0-based索引
    }
    else
    {
        return "(" + buildOptimalParens(s, i, s[i][j]) + "," + buildOptimalParens(s, s[i][j] + 1, j) + ")";
    }
}

int main()
{
    vector<int> dims;
    string fileName = "../data/matrix_chain-github-input_04.txt";
    ifstream inputFile(fileName);
    if (!inputFile)
    {
        cerr << "无法打开文件: " << fileName << endl;
        return 1;
    }

    int numMatrices;
    inputFile >> numMatrices; // 读取矩阵数量

    int rows, cols;
    inputFile >> rows >> cols; // 读取第一个矩阵的维度
    dims.push_back(rows);
    dims.push_back(cols);

    // 读取剩余矩阵的维度
    for (int i = 1; i < numMatrices; i++)
    {
        inputFile >> rows >> cols;
        dims.push_back(cols); // 只需存储前一个矩阵的列和当前矩阵的列
    }

    inputFile.close();

    // 输出解析后的矩阵维度
    // cout << "解析后的矩阵维度: ";
    // for (int d : dims)
    //     cout << d << " ";
    // cout << endl;

    if (dims.size() < 2)
    {
        cerr << "错误: 矩阵维度数据不足" << endl;
        return 1;
    }

    pair<vector<vector<int>>, vector<vector<int>>> result = matrixChainOrder(dims);
    vector<vector<int>> m = result.first;
    vector<vector<int>> s = result.second;

    cout << "最优标量乘法次数: " << m[1][dims.size() - 1] << endl;
    cout << "最优括号化方案: " << buildOptimalParens(s, 1, dims.size() - 1) << endl;

    return 0;
}
